tags:
  - DSA

DS. Red-Black Tree

Properties of Red Black Tree

红黑树是一颗自平衡的二叉搜索树，红黑树有 5 个属性，这五个属性都满足时，我们就说红黑树是平衡的。由于其属性，在每次增删改查时，红黑树都需要不断地进行调整，所以它是自平衡的。红黑树的属性是：

每个节点要么是红节点，要么是黑节点。（红黑树名字的由来）
根节点总是黑节点。
每个 NIL 节点（即叶子节点）都是黑节点。
每个红节点的子节点必须都要是黑节点。
从根节点到任意叶子节点之间的所有路径中，黑节点的数量总是一样的。
为了满足 5 ，红黑树每次加入节点时，初始颜色总是红色的。

Red Black Tree Cases

当你在红黑树中插入一个节点时，插入的节点会被默认设定为红节点。为什么？因为上面的第五条规则，从根节点到任意 nil 节点之间黑节点的个数都应当是相同的。插入红节点不会造成影响。之后，如果两个红节点连在一起，我们就需要修正红黑树（颜色翻转、旋转），平衡红黑树。

Case 1

插入一个子节点（红节点）。但是 uncle node 是红结点，这时候，切换 grandparent node 和 parent/uncle node 的颜色。（颜色翻转）

初始状态：
	 ...
	  /
   ● G(黑)
    /   \
 ○ P(红) ○ U(红)

插入N(红)后：
	 ...
	  /
   ● G(黑)
    /   \
 ○ P(红) ○ U(红)
  /
○ N(红) ← 冲突！

颜色翻转：
	 ...
	  /
   ○ G(红)
    /   \
 ● P(黑) ● U(黑)
  /
○ N(红)

Case 2

插入一个子节点（红节点）。Parent node 是红节点，而且 uncle node 是黑结点，这时候，旋转。

初始状态：
	 ...
	  /
   ● G(黑)
    /   \
 ○ P(红) ● U(黑)

插入N(红)后：
	 ...
	  /
   ● G(黑)
    /   \
 ○ P(红) ● U(黑)
    \
   ○ N(红) ← 冲突！

P节点左旋：转换成 Case 3
	 ...
	  /
   ● G(黑)
    /   \
 ○ N(红) ● U(黑)
  /
○ P(红)

Case 3

初始状态：
	 ...
	  /
   ● G(黑)
    /   \
 ○ P(红) ● U(黑)
  /
○ N(红)

旋转 grandparent node
	 ...
	  /
   ○ P(红)
    /   \
 ○ N(红) ● G(黑)
		  \
		  ● U(黑)

最终形态：
	 ...
	  /
   ● P(黑)
    /   \
 ○ N(红) ○ G(红)
		  \
		  ● U(黑)

Red Black Tree Insertion

我们要插入 1, 2, 3, 4, 5, 6

Inserting 1

○ 1(红)
/   \
NIL NIL

由于根节点必须是黑节点:

● 1(黑)
/   \
NIL NIL

Inserting 2

● 1(黑)
/   \
NIL ○ 2(红)
	/   \
   NIL  NIL

Inserting 3

● 1(黑)
/   \
NIL ○ 2(红)
	/   \
   NIL  ○ 3(红)
	    /   \
	   NIL  NIL

冲突发生，回到我们 Case 3, 翻转 grandparent node

	○ 2(红)
	/   \
● 1(黑) ○ 3(红)
/   \     /   \
NIL	NIL  NIL  NIL

翻转颜色：
	● 2(黑)
	/   \
○ 1(红) ○ 3(红)
/   \     /   \
NIL	NIL  NIL  NIL

Inserting 4

	● 2(黑)
	/   \
○ 1(红) ○ 3(红)
/   \     /   \
NIL	NIL  NIL  ○ 4(红)
			  /   \
             NIL  NIL

冲突发生，回到 Case 1 的情况：颜色翻转

	○ 2(红)
	/   \
● 1(黑) ● 3(黑)
/   \     /   \
NIL	NIL  NIL  ○ 4(红)
			  /   \
             NIL  NIL

根节点需要是黑节点：

	● 2(黑)
	/   \
● 1(黑) ● 3(黑)
/   \     /   \
NIL	NIL  NIL  ○ 4(红)
			  /   \
             NIL  NIL

Inserting 5

	● 2(黑)
	/   \
● 1(黑) ● 3(黑)
/   \     /   \
NIL	NIL  NIL  ○ 4(红)
			  /   \
             NIL  ○ 5(红)
	              /   \
	             NIL  NIL

回到 Case 3：

	● 2(黑)
	/    \
● 1(黑)  ○ 4(红)
/    \    /    \
NIL	NIL ● 3(黑) ○ 5(红)
		/    \   /    \
      NIL   NIL NIL  NIL

Recoloring:

	● 2(黑)
	/    \
● 1(黑)  ● 4(黑)
/    \    /    \
NIL	NIL ○ 3(红) ○ 5(红)
		/    \   /    \
      NIL   NIL NIL  NIL

Inserting 6


	● 2(黑)
	/    \
● 1(黑)  ● 4(黑)
/    \    /    \
NIL	NIL ○ 3(红) ○ 5(红)
		/    \   /    \
      NIL   NIL NIL  ○ 6(红)
					/   \
				  NIL   NIL
回到 Case 1:

	● 2(黑)
	/    \
● 1(黑)  ○ 4(红)
/    \    /    \
NIL	NIL ● 3(黑) ● 5(黑)
		/    \   /    \
      NIL   NIL NIL  ○ 6(红)
				    /   \
				  NIL   NIL

Traversal a Node

红黑树是自平衡的二叉搜索树，通过中序遍历，你就可以按顺序地得按顺序排列的节点（在这个例子中是从小到大）。

中序遍历的顺序是：左子树->根节点->右子树